#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1'000'001;

int min_prime_global[MAXN];
bool sieve_done = false;

void sieve_once(int n)
{
    if (sieve_done)
        return;
    for (int i = 2; i <= n; ++i)
    {
        if (min_prime_global[i] == 0)
        {
            min_prime_global[i] = i;
            for (long long j = (long long)i * i; j <= n; j += i)
            {
                if (min_prime_global[j] == 0)
                {
                    min_prime_global[j] = i;
                }
            }
        }
    }
    sieve_done = true;
}

vector<int> get_prime_factors_global(int n)
{
    if (n == 1)
        return {};
    vector<int> factors;
    while (n > 1)
    {
        int p = min_prime_global[n];
        if (p == 0)
        {
            factors.push_back(n);
            break;
        }
        factors.push_back(p);
        while (n > 1 && n % p == 0)
        {
            n /= p;
        }
    }
    return factors;
}

class Solution
{
public:
    int minJumps(vector<int> &nums)
    {
        int max_val = 0;
        for (int x : nums)
            max_val = max(x, max_val);
        sieve_once(max_val);

        int n = nums.size();
        if (n <= 1)
        {
            return 0;
        }

        unordered_map<int, vector<int>> prime_to_indices;
        for (int i = 0; i < n; ++i)
        {
            vector<int> factors = get_prime_factors_global(nums[i]);
            for (int p : factors)
            {
                prime_to_indices[p].push_back(i);
            }
        }

        queue<pair<int, int>> q;
        q.push({0, 0});

        vector<bool> visited_idx(n, false);
        unordered_set<int> visited_primes;
        visited_idx[0] = true;

        while (!q.empty())
        {
            auto [curr_idx, jumps] = q.front();
            q.pop();
            cout << curr_idx << endl;
            if (curr_idx == n - 1)
            {
                return jumps;
            }

            int number = nums[curr_idx];

            if (curr_idx + 1 < n && !visited_idx[curr_idx + 1])
            {
                visited_idx[curr_idx + 1] = true;
                q.push({curr_idx + 1, jumps + 1});
            }
            if (curr_idx - 1 >= 0 && !visited_idx[curr_idx - 1])
            {
                visited_idx[curr_idx - 1] = true;
                q.push({curr_idx - 1, jumps + 1});
            }

            if (number > 1 && min_prime_global[number] == number &&
                !visited_primes.count(number))
            {
                for (int next_idx : prime_to_indices[number])
                {
                    if (!visited_idx[next_idx])
                    {
                        visited_idx[next_idx] = true;
                        q.push({next_idx, jumps + 1});
                    }
                }
                visited_primes.insert(number);
            }
        }
        return -1;
    }
};

vector<int> split(const string &st, const string &token)
{
    vector<int> res;

    int length_of_token = token.size();
    size_t pos = 0;
    for (size_t edpos = st.find(token, pos);
         edpos != string::npos;
         pos = edpos + length_of_token, edpos = st.find(token, pos))
    {
        res.push_back(atoi(st.substr(pos, edpos - pos).c_str()));
    }
    if (pos < st.size())
        res.push_back(atoi(st.substr(pos).c_str()));
    return res;
}

int main()
{
    string line;
    getline(cin, line);
    vector<int> nums = split(line, " ");
    int output = Solution().minJumps(nums);
    cout << output << endl;
    return 0;
}